package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/2/26 18:06
 * @description <p>行星碰撞</p>
 */

import java.lang.reflect.Array;
import java.util.*;

/**
 * 题目：输入一个表示小行星的数组，数组中每个数字的绝对值表示小
 * 行星的大小，数字的正负号表示小行星运动的方向，正号表示向右飞行，
 * 负号表示向左飞行。如果两颗小行星相撞，那么体积较小的小行星将会爆
 * 炸最终消失，体积较大的小行星不受影响。如果相撞的两颗小行星大小相
 * 同，那么它们都会爆炸消失。飞行方向相同的小行星永远不会相撞。求最
 * 终剩下的小行星。例如，有 6 颗小行星[4, 5, -6, 4, 8, -5]，如图 6.2 所示（箭
 * 头表示飞行的方向），它们相撞之后最终剩下 3 颗小行星[-6, 4, 8]。
 */

public class toOffer6_2_37 {
    public static void main(String[] args) {
        int[] asteroids = {10, 2, -5};
        for (int i : asteroidCollision(asteroids)) {
            System.out.print(i + " ");
        }
    }

    /**
     * 方法二
     */
    public static int[] asteroidCollision(int[] asteroids) {

        LinkedList<Integer> stack = new LinkedList<>();
        for (int asteroid : asteroids) {
            //栈外的数一直向站内撞
            while (!stack.isEmpty() && -asteroid > stack.peek() && stack.peek() > 0) {
                stack.pop();
            }
            //栈外的数和栈顶的数撞碎了
            if (!stack.isEmpty() && asteroid < 0 && stack.peek() == -asteroid) {
                stack.pop();
            } else if (stack.isEmpty() || asteroid > 0 || stack.peek() < 0) {
                //栈外的数进栈
                stack.push(asteroid);
            }
        }

        Collections.reverse(stack);
        return stack.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 方法一
     * 思想：
     * 只有当栈不为空，且顶层是正数、下一个要加进来的数是负数的时候，才会发生碰撞
     * 只有当栈外的数在碰撞之后存活下来，才会加入栈
     *
     * @param asteroids
     * @return
     */
    public static int[] asteroidCollision1(int[] asteroids) {
        //构造栈
        LinkedList<Integer> stack = new LinkedList<>();
        for (int asteroid : asteroids) {
            boolean flag = true;
            while (flag && !stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {
                //判断栈外要加的数是否存在，存在后面就会加入栈中，不存在就证明被撞碎了
                flag = stack.peek() < -asteroid;
                //发生碰撞，需要进行比较
                if (stack.peek() <= -asteroid) {
                    stack.pop();
                }
            }

            if (flag) {
                //往栈里加数
                stack.push(asteroid);
            }
        }

        Collections.reverse(stack);
        return stack.stream().mapToInt(Integer::intValue).toArray();
    }
}
